Service scheduling is the primary mechanism for providing Quality of Service (QoS) guarantees on a per-VC basis in Asynchronous Transfer Mode (ATM) networks. Such service scheduling schemes must satisfy a number of requirements in order to be used in practical ATM switches and multiplexers. Firstly, such a service scheduling scheme must guarantee specified service rate to each virtual connection (VC), irrespective of the traffic patterns in the VCS. Secondly, the scheduling scheme must flexibly allocate excess (i.e., temporarily unused and unallocated) bandwidth among the active VCs. Thirdly, the outgoing traffic streams of each VC and VPs must be smooth (shaped) and not bursty. Fourthly, the service rate given to a VC or a group of VCs must not exceed a specified upper bound. Most importantly, the scheduling algorithm must be simple so that the scheduling decision can be performed using only a few operations per cell time.
Previously proposed schemes such as the Weighted Round Robin (WRR), Packetized Generalized Processor Sharing (PGPS) [A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single node case. IEEE/ACM Transactions on Networking, 1(3):344-357, June 1993; S. Demers, A. Keshav and S. Shenker. Analysis and simulation of a fair queuing algorithm. Internet Research and Experience, 1, 1990, incorporated by reference herein], Self-Clocked Fair Queueing (SCFQ) [S. J. Golestani. A self-clocked fair queuing scheme for broadband applications. In Proceedings of IEEE INFOCOM, pages 636-646, June 1994, incorporated by reference herein], Worst Case Fair Weighted Fair Queueing (WF2Q) [C. R. Bennet and H. Zhang. WF2Q: Worst-case fair weighted fair queuing. In Proceedings of IEEE INFOCOM, pages 120-128, 1996, incorporated by reference herein], and Virtual Clock [L. Zhang. Virtualclock: A new traffic control algorithm for packet switched networks. ACM Transactions on Computer Systems, 9(2):101-124, May 1991, incorporated by reference herein] have either fallen short of these goals or are too complex to be implemented in high speed hardware cost-effectively.